﻿// Copyright (c) 2006, Inc.
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//
// Author: arvin.chen
//
//

#ifndef ALGORITHM_SORT_BUCKET_H_
#define ALGORITHM_SORT_BUCKET_H_
#include <algorithm>
#include <functional>

#ifndef ALGORITHM_SORT_BASE_H_
#include "algorithm/sort/base.h"
#endif

namespace algorithm {
	namespace sort {
		class Bucket : public Base<int> {
		public:

			/**
			* Construction
			*
			* @param
			* @return
			*/
			Bucket() :
				Base<int>::Base(kBucket)
			{
				
			}

			/**
			* Destruction
			*
			* @param VOID
			* @return
			*/
			~Bucket()
			{

			}

			/**
			* sort
			*
			* @param int arr[]
			* @param int len
			* @return int
			*/
			virtual int* sort(int arr[], int len)
			{
				if (nullptr == arr || 1 >= len) return arr;
				int max = arr[0];
				int min = arr[0];
				// Find the maximum and minimum values ​​of the array
				for (int i = 1; i < len; i++) {
					if (min > arr[i])
						min = arr[i];
					if (max < arr[i])
						max = arr[i];
				}
				//Same as the counting sorting of the optimized version, get an offset value of min
				int d = max - min;
				//Create d / bucket_step + 1 buckets, the i-th bucket stores numbers in the range of bucket_step*i ~ bucket_step*i+bucket_step-1
				int bucket_step = 5;
				int bucket_num = d / bucket_step + 1;
				std::vector<std::vector<int>> bucket_vector(bucket_num);
				//Initialize the bucket
				for (int i = 0; i < bucket_num; i++) {
					bucket_vector.push_back(std::vector<int>());
				}
				//Traverse the original array and put each element into the bucket
				for (int i = 0; i < len; i++) {
					bucket_vector[(arr[i] - min) / bucket_step].push_back(arr[i] - min);
				}
				//Sorting the elements in the bucket, I use the sorting tool that comes with the system here
				for (int i = 0; i < bucket_num; i++) {
					std::sort(bucket_vector[i].begin(), bucket_vector[i].end());
				}
				//Merge the sorted data of each bucket and put it back into the original array
				int k = 0;
				for (int i = 0; i < bucket_num; i++) {
					for (size_t t = 0; t < bucket_vector[i].size(); t++) {
						arr[k++] = bucket_vector[i][t];
					}
				}
				return arr;
			}

		protected:
			/**
			* Assignment
			*
			* @param const Bucket& cbase
			* @return Bucket&
			*/
			Bucket& operator=(const Bucket& cbase);

			/**
			* Copy Construction
			*
			* @param const Bucket& cbase
			* @return
			*/
			Bucket(const Bucket& cbase);

		private:

		public:
		protected:
		private:

		};
	} // namespace algorithm 
} // namespace sort


#endif  // ALGORITHM_SORT_BUCKET_H_
